package com.study.algorithm.pathalgorithm.MIniTree.impl;

import com.study.algorithm.datastruct.graph.model.Edge;
import com.study.algorithm.datastruct.graph.model.Graph;
import com.study.algorithm.datastruct.graph.model.Vertex;
import com.study.algorithm.datastruct.tree.model.Tree;

import java.util.*;
import java.util.stream.Collectors;


/**
 * 该算法是按照无向图走的
 */
public class Kruskal extends MiniSpanningTreeImpl {


    /**
     * 该算法对图的要求是应该能满足一个基本点
     * 给图中任意一个顶点A，那么A到其它顶点都至少有一个通路，才能生成最小生成树
     * 至于检测算法，没有写，如果你有兴趣可以自己完成
     * `
     *
     * @param graph
     * @return
     */
    @Override
    public Tree getMiniSpanningTree(Graph graph) {
        Set<Vertex> vertices = graph.getVertices();
        int verticeSize = vertices.size();
        Set<Edge> edges = sortEdgesDesc(graph.getEdges());
        Set<Edge> selectedEdge = new HashSet<>();
        Set<Vertex> selectedVerties = new HashSet<>();
//        Set<Vertex> isolatedVerties = new HashSet<>();//不可达点集合（孤立的点）

        Iterator<Edge> it = edges.iterator();
        while (it.hasNext() || selectedEdge.size() == verticeSize - 1) {
            Edge currSelectEdge = it.next();
            it.remove();
            Integer currDistance = currSelectEdge.getDistance();
            //如果距离为不可达点，结束循环（集合是已经排序好的，所以后边都是不可达点)
            if (currDistance == null || currDistance == -1) {
//                addTheVertexToIsolated(currSelectEdge, selectedVerties, isolatedVerties);
//                continue;
                break;
            }

            //标记已经选择出来的顶点和边
            addTheVertexAndEdgeToSelected(currSelectEdge, selectedEdge, selectedVerties);
        }


        return generateTreeThroughEdges(vertices, selectedEdge);
    }

    private void addTheVertexAndEdgeToSelected(Edge edge, Set<Edge> selectedEdge, Set<Vertex> selectedVerted) {

        Vertex vertex1 = edge.getStartVetex();
        Vertex vertex2 = edge.getEndVetex();

        boolean isSelectedForVertex1 = selectedVerted.contains(vertex1);
        boolean isSelectedForVertex2 = selectedVerted.contains(vertex2);
        if (isSelectedForVertex1 && isSelectedForVertex2) {
            Set<Edge> copyEdge = selectedEdge.stream().collect(Collectors.toSet());
            if (isExistPathFromVertexToVertex(copyEdge, vertex1, vertex2)) {
                return;
            }

        }
        selectedEdge.add(edge);
        if (!isSelectedForVertex1) {
            selectedVerted.add(vertex1);
        }

        if (!isSelectedForVertex2) {
            selectedVerted.add(vertex2);
        }

    }


    private void addTheVertexToIsolated(Edge edge, Set<Vertex> selectedVerties, Set<Vertex> isolatedVerties) {

        Vertex vertex1 = edge.getStartVetex();
        Vertex vertex2 = edge.getEndVetex();

        boolean isSelectedForVertex1 = selectedVerties.contains(vertex1);
        boolean isSelectedForVertex2 = selectedVerties.contains(vertex2);
        boolean isIsolateForVertex1 = isolatedVerties.contains(vertex1);
        boolean isIsolateForVertex2 = isolatedVerties.contains(vertex2);

        if (!isSelectedForVertex1 && !isIsolateForVertex1) {
            isolatedVerties.add(vertex1);
        }

        if (!isSelectedForVertex2 && !isIsolateForVertex2) {
            isolatedVerties.add(vertex2);
        }

    }

}
